package com.datastructures2.字符串.子字符串查找;

import java.math.BigInteger;
import java.util.Random;

/**
 * Rabin-Karp指纹字符串查找算法
 * @author MaoLin Wang
 * @date 2020/2/2815:24
 */
public class RK {
    private String pat;

    /**
     * 模式字符串的散列值
     */
    private long patHash;
    /**
     * 模式字符串长度
     */
    private int M;

    /**
     * 一个很大的素数
     */
    private long Q;
    /**
     * 字母表大小
     */
    private int R=256;

    /**
     * R^(R-1) % Q
     */
    private long RM;

    public RK(char[] pattern, int R) {
        this.pat = String.valueOf(pattern);
        this.R = R;
        throw new UnsupportedOperationException("Operation not supported yet");
    }

    public RK(String pat) {
        this.pat = pat;
        R = 256;
        M = pat.length();
        Q = longRandomPrime();

        // precompute R^(R-1) % Q for use in removing leading digit
        RM = 1;
        for (int i = 1; i <= M-1; i++)
            RM = (R * RM) % Q;
        patHash = hash(pat, M);
    }

    private long hash(String key, int M) {
        long h = 0;
        for (int j = 0; j < M; j++)
            h = (R * h + key.charAt(j)) % Q;
        return h;
    }

    private boolean check(String txt, int i) {
        for (int j = 0; j < R; j++)
            if (pat.charAt(j) != txt.charAt(i + j))
                return false;
        return true;
    }

    // Monte Carlo version: always return true
    // private boolean check(int i) {
    //    return true;
    //}

    /**
     * Returns the index of the first occurrrence of the pattern string
     * in the text string.
     *
     * @param  txt the text string
     * @return the index of the first occurrence of the pattern string
     *         in the text string; n if no such match
     */
    public int search(String txt) {
        int n = txt.length();
        if (n < R) return n;
        long txtHash = hash(txt, R);

        // check for match at offset 0
        if ((patHash == txtHash) && check(txt, 0))
            return 0;

        // check for hash match; if hash match, check for exact match
        for (int i = M; i < n; i++) {
            txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q;
            txtHash = (txtHash*R + txt.charAt(i)) % Q;

            // match
            int offset = i - M + 1;
            if ((patHash == txtHash) && check(txt, offset))
                return offset;
        }

        // no match
        return n;
    }

    public static void main(String[] args) {
        String s="sadsadasf";
        RK ds = new RK("ds");
        int search = ds.search(s);
        System.out.println(search);
    }

    // a random 31-bit prime
    private static long longRandomPrime() {
        BigInteger prime = BigInteger.probablePrime(31, new Random());
        return prime.longValue();
    }
}
